#define _CRT_SECURE_NO_WARNINGS 1
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<unordered_map>
using namespace std;

class Solution {
public:
    vector<int> tmp;
    int sum = 0;
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size(), 0);
        mergsort(nums, 0, nums.size() - 1);
        return sum;
    }

    void mergsort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;

        int mid = left + (right - left) / 2;
        mergsort(nums, left, mid);
        mergsort(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid)
        {
            while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
            if (cur2 > right) break;
            sum += right - cur2 + 1;
            cur1++;
        }

        cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right) tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];
        for (int i = left; i <= right; i++)
        {
            nums[i] = tmp[i - left];
        }
        return;
    }
};

int main() {
    vector<int> arr = { -5,-5 };
    int ret = Solution().reversePairs(arr);
    return 0;
}